package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 最长递增子序列查找器
 * 
 * @author csy
 * @description 给定一个无序的整数数组，找到其中最长上升子序列的长度
 * 
 *              解题思路：
 *              1. 使用动态规划求解，dp[i]表示以nums[i]结尾的最长递增子序列长度
 *              2. 对于每个位置i，查找其之前的所有位置j：
 *              - 如果nums[i] > nums[j]，说明可以接在j后面形成更长的递增序列
 *              - dp[i] = max(dp[i], dp[j] + 1)
 *              3. 最终结果是dp数组中的最大值
 * 
 *              时间复杂度：O(n^2)，其中n为数组长度
 *              空间复杂度：O(n)，需要dp数组存储中间结果
 * 
 *              示例：
 *              输入: [10,9,2,5,3,7,101,18]
 *              输出: 4
 *              解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4
 * 
 *              参考：https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */
public class LongestIncreasingSubsequence {

    /**
     * 查找最长递增子序列的长度
     *
     * @param nums 输入数组
     * @return 最长递增子序列的长度
     */
    public static int findLongestIncreasingSubsequence(int[] nums) {
        // 处理边界情况
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // dp[i]表示以nums[i]结尾的最长递增子序列长度
        int[] dp = new int[nums.length];
        // 初始化dp数组，每个元素自身可以形成长度为1的子序列
        Arrays.fill(dp, 1);

        // 记录最长递增子序列的长度
        int maxLength = 1;

        // 遍历每个位置，计算以其结尾的最长递增子序列长度
        for (int i = 1; i < nums.length; i++) {
            // 查找位置i之前的所有元素
            for (int j = 0; j < i; j++) {
                // 如果当前元素大于之前的元素，可以形成递增序列
                if (nums[i] > nums[j]) {
                    // 更新dp[i]为max(dp[i], dp[j] + 1)
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新全局最大长度
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试用例
        int[][] testCases = {
                { 10, 9, 2, 5, 3, 7, 101, 18 }, // 期望输出：4 ([2,3,7,101])
                { 0, 1, 0, 3, 2, 3 }, // 期望输出：4 ([0,1,2,3])
                { 7, 7, 7, 7, 7, 7, 7 }, // 期望输出：1 ([7])
                { 1, 3, 6, 7, 9, 4, 10, 5, 6 } // 期望输出：6 ([1,3,6,7,9,10])
        };

        // 执行测试
        for (int[] nums : testCases) {
            System.out.println("输入数组：" + Arrays.toString(nums));
            int result = findLongestIncreasingSubsequence(nums);
            System.out.printf("最长递增子序列的长度为：%d%n%n", result);
        }
    }

    /**
     * 打印dp数组（用于调试）
     */
    private static void printDpArray(int[] nums, int[] dp) {
        System.out.println("DP数组状态：");
        for (int i = 0; i < nums.length; i++) {
            System.out.printf("nums[%d]=%d, dp[%d]=%d%n",
                    i, nums[i], i, dp[i]);
        }
        System.out.println();
    }
}